package 图论.所有可能的路径_797;

import java.util.ArrayList;
import java.util.List;

/*
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

*/
public class Solution {
    static List<List<Integer>> arr; // 存所有答案路径
    static List<Integer> ans;  // 存某条路径
    public static void main(String[] args) {
        int[][] graph = {{1,2},{3},{3},{}};
        List<List<Integer>> arr2 = allPathsSourceTarget(graph);
        for (List<Integer> t : arr2){
            for (Integer k : t){
                System.out.println(k);
            }
        }

    }

    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 初始化两个链表
        arr = new ArrayList<>();
        ans = new ArrayList<>();
        // 将第一个节点添加进去，再dfs搜索
        ans.add(0);
        dfs(graph, 0);
        return arr;
    }

    static void dfs(int[][] graph, int node){
        // 结束状态： 当与目前节点能到达的最后一个数字遍历完了就可以退出了
        if (node == graph.length - 1){
            arr.add(new ArrayList<>(ans));
            return;
        }
        // 遍历节点能到达的点
        for (int i = 0; i < graph[node].length; i ++){
            // 记录下一个到达的节点
            int nextnode = graph[node][i];
            // 加入链表
            ans.add(nextnode);
            // 递归添加
            dfs(graph, nextnode);
            // 如果没满足结束条件就回溯
            ans.remove(ans.size() - 1);
        }

    }
}
